﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
// 原题连接：https://leetcode.cn/problems/swap-nodes-in-pairs/
/*
题目描述：
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。
你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

 
示例 1：
输入：head = [1,2,3,4]
输出：[2,1,4,3]

示例 2：
输入：head = []
输出：[]

示例 3：
输入：head = [1]
输出：[1]

提示：
链表中节点的数目在范围 [0, 100] 内
0 <= Node.val <= 100
*/

// Definition for singly-linked list.
struct ListNode {
     int val;
     struct ListNode *next;
 };
 

// 方法1——使用新的链表
// 开始解题
struct ListNode* swapPairs(struct ListNode* head) {
    if (NULL == head) {
        return NULL;
    }
    if (NULL == head->next) {
        return head;
    }
    struct ListNode* newhead = NULL;
    struct ListNode* cur = head;
    struct ListNode* next = NULL; // 记录从cur的下一个节点，方便cur往后走
    struct ListNode* tail = newhead; // 记录新链表的尾节点
    struct ListNode* pre = newhead; // 记录新链表的尾节点的前一个节点
    int len = 0; // 记录链表的长度
    while (cur) {
        len++;
        next = cur->next;
        if (len % 2 == 1) {
            // 如果len是奇数，就尾插到链表的最后
            if (NULL == newhead) {
                newhead = cur;
                tail = cur;
                pre = newhead;
                tail->next = NULL;
            }
            else {
                tail->next = cur;
                tail = tail->next;
                tail->next = NULL;
            }
            if (len >= 3) {
                pre = pre->next;
            }
        }
        else {
            // 如果len是偶数，那就插入到pre和tail之间
            if (pre == newhead) {
                cur->next = newhead;
                newhead = cur;
                pre = newhead;
            }
            else {
                cur->next = tail;
                pre->next = cur;
                pre = pre->next;
            }
        }
        cur = next;
    }
    return newhead;
}